/**
 * 35. 搜索插入位置
 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 你可以假设数组中无重复元素。
 示例 1:
 输入: [1,3,5,6], 5
 输出: 2
 示例 2:
 输入: [1,3,5,6], 2
 输出: 1
 示例 3:
 输入: [1,3,5,6], 7
 输出: 4
 示例 4:
 输入: [1,3,5,6], 0
 输出: 0
 */
public class A622 {
    public static void main(String[] args) {
        int[] nums = {1,3,5,7};
        int target = 5;
        Solution622 so = new Solution622();
        int i = so.searchInsert(nums, target);
        System.out.println(i);

    }
}

class Solution622 {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        for (int i = 0; i < len ; i++) {
            if(nums[i] == target)
                return i;
        }

        for (int i = 0; i < len; i++) {
            if(target < nums[0]){
                return 0;
            }else if(target > nums[len - 1]){
                return len;
            }else if(target > nums[i] && target < nums[i + 1] && i < (len - 1)){
                return i + 1;
            }else  if(target > nums[len - 2] && target < nums[len - 1]){
                return len -1;
            }
        }



        return -1;

    }
}
/**
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
 内存消耗：39.3 MB, 在所有 Java 提交中击败了5.55%的用户
 */

 /* if(target < nums[0]){
                return 0;
            }else if(nums[i] == target ){
                return i;
            }else if(nums[nums.length - 1] == target){
                return nums.length - 1;
            } else if(target > nums[i] && target < nums[i + 1]){
                return i + 1;
            }else if(target > nums[nums.length - 1]) {
                return nums.length;
            }*/